// 查并集
class UnionFind
{
private:
	vector<int> parent;
	vector<int> size;
	int setCount;                  // 当前连通分量的数目
public:
	UnionFind(int n) :setCount(n), parent(n), size(n, 1)
	{
		iota(parent.begin(), parent.end(), 0);
	}

	int findset(int x)
	{
		return parent[x] == x ? x : findset(parent[x]);
	}

	bool unite(int x, int y)
	{
		x = findset(x), y = findset(y);
		if (x == y)
		{
			return false;
		}
		if (size[x] < size[y])
		{
			swap(x, y);
		}
		parent[y] = x;
		size[x] += size[y];
		--setCount;
		return true;
	}
	bool IsConnected(int x, int y)
	{
		return findset(x) == findset(y);
	}
};

class Solution
{
public:
	int minimumEffortPath(vector<vector<int>>& heights)
	{
		int numRow = heights.size(), numCol = heights.front().size();
		vector<tuple<int, int, int>> edges;
		for (size_t cntRow = 0; cntRow < numRow; cntRow++)
		{
			for (size_t cntCol = 0; cntCol < numCol; cntCol++)
			{
				int index = cntRow * numCol + cntCol;
				if (cntRow > 0)
				{
					edges.emplace_back(index - numCol, index, abs(heights[cntRow][cntCol] - heights[cntRow - 1][cntCol]));
				}
				if (cntCol > 0)
				{
					edges.emplace_back(index - 1, index, abs(heights[cntRow][cntCol - 1] - heights[cntRow][cntCol]));
				}
			}
		}
		sort(edges.begin(), edges.end(), [&](tuple<int, int, int>& elem1, tuple<int, int, int>& elem2)
			{
				int x, y;
				tie(ignore, ignore, x) = elem1;
				tie(ignore, ignore, y) = elem2;
				return x < y;

			});

		UnionFind uf(numCol * numRow);
		int ret = 0;
		vector<tuple<int, int, int>>::iterator iter = edges.begin();
		for (; iter != edges.end(); iter++)
		{
			int x, y, v;
			tie(x, y, v) = *iter;
			uf.unite(x, y);
			if (uf.IsConnected(0, numRow * numCol - 1))
			{
				ret = v;
				break;
			}
		}
		return ret;
	}
};